

int kthToLast(struct ListNode* head, int k) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    int i = 0;
    for (i = 0; i < k; i++)
    {
        fast = fast->next;
    }
    while (fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow->val;
}

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* cur = head;
    struct ListNode* ptre = NULL;
    while (cur)
    {
        if (cur->val != val)
        {
            ptre = cur;
            cur = cur->next;
        }
        else
        {
            if (ptre == NULL)
            {
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {
                ptre->next = cur->next;
                free(cur);
                cur = ptre->next;
            }

        }
    }
    return head;
}


struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* new = NULL;
    struct ListNode* head = NULL;
    while (list1->next && list2->next)
    {
        if (list1->val > list2->val)
        {
            new = list2;
            list1 = list1->next;
        }
        else
        {
            new = list1;
            list2 = list2->next;
        }
    }
}


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy;
    struct ListNode* new = &dummy;
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            new->next = list1;
            list1 = list1->next;
        }
        else
        {
            new->next = list2;
            list2 = list2->next;
        }
        new = new->next;
    }
    if (list1)
    {
        new->next = list1;
    }
    else
    {
        new->next = list2;
    }
    return dummy.next;
}

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur1 = head;
    struct ListNode* new = NULL;

    while (cur1)
    {
        struct ListNode* cur2 = cur1->next;

        cur1->next = new;
        new = cur1;

        cur1 = cur2;
    }
    return new;
}

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = n2->next;
    //struct ListNode* newhead = n2;

    while (n2)
    {
        n2->next = n1;

        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* gGuard, * lGuard, * gTail, * lTail;
        struct ListNode* cur = pHead;
        gGuard = gTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lGuard = lTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        gGuard->next = lGuard->next = NULL;
        while (cur)
        {
            if (cur->val < x)
            {
                gTail->next = cur;
                gTail = gTail->next;
            }
            else
            {
                lTail->next = cur;
                lTail = lTail->next;
            }
            cur = cur->next;
        }
        gTail->next = lGuard->next;
        lTail->next = NULL;
        pHead = gGuard->next;
        free(gGuard);
        free(lGuard);
        return pHead;
    }
};


bool chkPalindrome(ListNode* head) {
    struct ListNode* mid = middleNode(head);
    struct ListNode* rmid = reverseList(mid);
    while (rmid) {
        if (rmid->val != head->val) {
            return false;
        }
        rmid = rmid->next;
        head = head->next;
    }
    return true;
}


struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* cur1 = headA;
    struct ListNode* cur2 = headB;
    int lenA = 1;
    int lenB = 1;
    while (cur1->next)
    {
        cur1 = cur1->next;
        lenA++;
    }
    while (cur2->next)
    {
        cur2 = cur2->next;
        lenB++;
    }
    if (cur1 != cur2)
        return NULL;
    int dft = abs(lenA - lenB);
    struct ListNode* fast = headA;
    struct ListNode* slow = headB;
    if (lenA < lenB)
    {
        slow = headA;
        fast = headB;
    }
    while (dft--)
    {
        fast = fast->next;
    }
    while (fast != slow)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}